package com.lwt.codetop.binaryTree;

// 236. 二叉树的最近公共祖先

/**
 * 思路：lca，背过即可
 *      最近公共祖先的特性：
 *          如果 p 和 q 分别在 root 的左右子树中，那么 root 就是 LCA
 *          如果 p 或 q 本身就是 LCA（即一个节点是另一个的祖先）
 */
public class LowestCommonAncestorOfABinaryTree {
    public static void main(String[] args) {
        // 构建测试用例
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(5);
        root.right = new TreeNode(1);
        // 补充 5 的子节点
        root.left.left = new TreeNode(6);
        root.left.right = new TreeNode(2);
        // 补充 2 的子节点
        root.left.right.left = new TreeNode(7);
        root.left.right.right = new TreeNode(4);
        // 补充 1 的子节点
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(8);

        // 求最近公共祖先
        // 正确的测试用例：使用树中已有的节点
        TreeNode p = root.left;          // p指向树中的节点5
        TreeNode q = root.left.right.right;  // q指向树中的节点4

        //          3
        //        /   \
        //       5     1
        //      / \   / \
        //     6  2  0   8
        //       / \
        //      7   4

        TreeNode res = dfs(root, p, q);
        System.out.println(res.val);

    }

    /**
     * 返回二叉树的最近公共祖先
     * @param root
     * @param p
     * @param q
     * @return
     */
    private static TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
        //
        if(root == null || root == p || root == q) return root;
        // 判断左右子树是否包含p q
        // 采用的是后序遍历的方式，也就是说自底向上的，那么找到的祖先就是最近的
        TreeNode left = dfs(root.left, p, q);
        TreeNode right = dfs(root.right, p, q);
        if(left == null) return right; // 如果左子树不包含p q，说明可能在右子树
        if(right == null) return  left;// 如果右子树不包含p q，说明可能在左子树
        return root; // 左右两边都不为空，即p q左右各一个，则此时根节点即为最近公共祖先
    }
}
